from collections import Counter


class Solution:
    def minWindow(self, s: str, t: str) -> str:
        if len(s) < len(t): return ""
        if Counter(t) - Counter(s): return ""
        counter = Counter(t)
        words = set(t)
        i = 0
        n = len(s)
        ans = s
        for j in range(n):
            if s[j] in words:
                counter[s[j]] -= 1
            while max(counter.values()) <= 0:
                if len(ans) > j - i + 1:
                    ans = s[i:j + 1]
                if s[i] in words:
                    counter[s[i]] += 1
                i += 1
        return ans

if __name__ == '__main__':
    S = Solution()
    r = S.minWindow(s="ADOBECODEBANC", t="ABC")
    print(r)
